/**
 * @file task_interval_schedule.cpp
 * @author Wang Bo (1276106221@qq.com)
 * @brief 任务调度问题（贪心算法）
 * 假设有一堆待办事项，有各自的开始时间和结束时间
 * 问：如何安排任务可以使得完成的任务数量最大
 * 思路：将结束时间按升序排序，若下一个任务开始时间早于当前任务结束时间
 * 则将其移出链表，直到没有重叠，则移动到下一个任务重复操作
 * @version 0.1
 * @date 2021-07-08
 * 
 * @copyright Copyright (c) 2021
 * 
 */
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <random>
using std::cout;
using std::endl;
using std::vector;
using std::string;
constexpr int MAX_RAND_NUM_ = 24;
std::random_device rd;
std::mt19937 mtrand(rd());
std::uniform_int_distribution<std::mt19937::result_type> dist(1, MAX_RAND_NUM_);

inline auto getRand() {
    return dist(mtrand);
};

struct Task {
    int id;
    int start;
    int end;
    bool operator<(const Task& that) const {
        return end < that.end;
    }
    friend std::ostream& operator<<(std::ostream& os, const Task& t) {
        os << "Task id: " << t.id << " start: " << t.start
           << " end: " << t.end;
        return os;
    }
};

int main() {
    std::list<Task> tasks;    
    for (int i = 0; i < 10; ++i) {
        int start, end;
        do {
            start = static_cast<int>(getRand());
            end = static_cast<int>(getRand());
        } while (start >= end);
        tasks.emplace_back(Task{i, start, end});
    }
    auto p = [](const std::list<Task>& l) {
        int totalTasks = 0;
        for (auto iter = l.begin(); iter != l.end(); ++iter)
        {
            totalTasks++;
            cout << *iter << endl;
        }
        cout << "total tasks:  " << totalTasks << endl << endl;
    };
    p(tasks);
    tasks.sort();
    p(tasks);
    for (auto iter = tasks.begin();
         iter != tasks.end(); ++iter)
    {
        auto nextIter = std::next(iter);
        while (nextIter != tasks.end() && nextIter->start < iter->end )
        {
            nextIter = tasks.erase(nextIter);
        }
    }
    p(tasks);
    return 0;
}